package com.cuz.series.linklist;

/**
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
 */
public class 链表7删除链表的倒数第N个结点 {
    public static void main(String[] args) {
        ListNode head = ListNode.of1(1, 2);
        removeNthFromEnd1(head, 2).print();
    }

    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        if (head == null || n <= 0) {
            return head;
        }
        int num = nodeNum(head);
        //只有一个节点 且删除倒数第一个
        if (num == 1 && n == 1) {
            return null;
        }
        //需要fast 前进多少步
        int fastNeedStep = num - n;
        //0 说明删除第一个 比如三个节点 删除倒数第三个 那么直接返回next
        if (fastNeedStep == 0) {
            return head.next;
        }
        //fast 前进
        ListNode fast = head;
        //pre 是fast的前置节点
        ListNode pre = new ListNode();
        pre.next = head;
        for (int i = 0; i < fastNeedStep; i++) {
            pre = pre.next;
            fast = fast.next;
        }
        //删除fast
        pre.next = fast.next;
        return head;
    }

    private static int nodeNum(ListNode node) {
        if (node == null) {
            return 0;
        }
        int num = 0;
        while (node != null) {
            num++;
            node = node.next;
        }
        return num;
    }
}
